//
//  93. 复原IP地址.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/28.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/**
 复原IP地址
 这个问题其实还是一个字符串分割的问题
 例如：25525511135;
 只要四个分割同时满足条件就就可以了。
 */
class Solution93 {
    var result: [String] = []
    var path: [String] = []
    func restoreIpAddresses(_ s: String) -> [String] {
        let ss = Array(s).map {String($0)}
        backTrace(ss: ss, start: 0)
        return result
    }
    func backTrace(ss: [String], start: Int) {
        if path.count > 4 {
            return
        }
        if path.count == 4 && start == ss.count {
            result.append(path.joined(separator: "."))
            return
        }
        for i in start..<ss.count {
            let sub = ss[start...i]
            let subStr = sub.joined()
            if isIPValid(s: ss, start: start, end: i) {
                path.append(subStr)
            } else {
                break
            }
            backTrace(ss: ss, start: i + 1)
            path.removeLast()
        }
    }
    func isIPValid(s: [String], start: Int, end: Int) -> Bool {
        // 0开头的数字不合法
        if s[start] == "0" && start != end {
            return false
        }
        var num = 0
        for i in start...end {
            // 遇到非法数字
            if s[i] > "9" || s[i] < "0" {
                return false
            }
            // 字符的相差值
            let si = (s[i] as NSString).intValue
            num = num * 10 + Int(si);
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true
    }
    static func test() {
        let str = "25525511135"
//        let str =  "0000"
//        let str = "1111"
        let solution = Solution93()
        let result = solution.restoreIpAddresses(str)
        print(result)
    }
}
